1. Field of Invention
This invention relates the recognition of patterns within digital signals and more particularly patterns within a serial bit stream.
2. Description of Related Art
In circuitry involved in transmitting packets of data such as disk drives and the Internet there is a need to identify patterns prior to starting data. One method used is to shift data into a shift register, and when the shift register is full, connect the data in the registers to a comparator to determine if the desired pattern is present. The time to make the comparison is the amount of time to shift the input data into the shift register plus the time to do the compare. As the number of bits of data to be compared increase this approach becomes less desirable.
In U.S. Pat. No. 5.459.754 (Newby et al.) a recognizer system including transmitting and receiving capability for a serial data stream uses a decision tree to recognize predetermined bit patterns to access a memory to retain previous states of comparison. When the system recognizes a final bit, a logical one is outputted to indicate the sought after pattern has been found. In U.S. Pat. No. 5.266.918 (Won et al.) a serial magnitude comparator is described in which compares input data values with an internal data value. The internal data value may be varied and the output of the comparator is a least significant bit and a most significant bit. In U.S. Pat. No. 4,524,345 (Sybel et al.) a high speed detector is described for detecting a flag character in a serial data stream. A pattern register is used to store a reference flag, pattern. As each bit in the serial data stream is received it is compared to each bit in the reference pattern using a set of comparators simultaneously.
When a pattern many bits long, needs to be detected in a serial bit stream, previous methods Would use an N-stage shift register which is long enough for the pattern needing detection. Once the shift register is filled with bits from the serial bit stream, all of the shift registers would output their bit value in parallel into a comparator circuit. The longer the pattern to be detected, the more stages that are required in the comparator, and the longer the delay before results are known. In today""s world of faster and faster communications determining packet identification on the fly requires faster search and find timing to be able to keep up with the communications.
It is the object of the present invention to overcome the aforementioned problems.
It is another object of the present invention to provide a comparator containing a shift register having minimal internal delays.
It is another object of the present invention to compare bits in a serial bit stream, accomplished within shift register circuitry resulting in only three circuit delays beyond the end of a pattern included within the bit stream, and where a bit in the serial bit stream is compared to all reference bits defining the pattern in parallel.
It is an additional object of the present invention to provide a comparator/shift register with minimal internal delays.
To accomplish a compare using circuitry within a shift register, the first stage of the comparing shift register compares the first bit in the serial bit stream to the first reference bit. The second stage compares the first bit in the serial bit stream to the second reference bit, and so on until the first bit in the serial bit stream is compared to the last reference bit in the last stage of the comparing shift register. The results in each stage is combined in an AND circuit with the results in the next stage which accumulates the results from stage to stage. The results from the AND circuit in the last stage is a composite of all the compares in all the previous stages. If a compare is not found the next bit in the serial bit stream is compared to all the reference bits, one reference bit for each stage of the comparing shift register. Again the results of the compare are combined with AND circuits in each stage, and the last AND circuit provides the accumulation of the compare results from the last stage and all previous stages. In providing this comparison a total of only three circuits of delay are required beyond the delay of the normal shift register of any length, all exclusive NOR circuit for comparing, an AND circuit for accumulating compare results and a multiplexer (MUX) for choosing compare or at straight shift register.
All stages of the comparing shift register are the same except the first stage which does not have an AND circuit since there is no compare results to accumulate prior to the first stage results. A connection from the output of the output register of the previous stage is connected directly to a first input of a MUX and to a first input of an AND circuit. The AND circuit output is connected to a second input of the MUX. Again the exception is the first stage where the output of the input register is connected directly to the MUX and to an exclusive NOR (XNOR) for comparing a bit of the serial bit stream to the first reference bit. The output of the input register is connected to a first input of the XNOR in each stage of the comparing shift register so that each bit of the serial bit stream is compared to each reference bit. The reference bit to which the bits in the serial bit stream are compared is connected to the second input of the XNOR. The reference bit can be different for each comparator in the comparing shift register. The MUX in each stage is selected for shifting or for comparing, and a clock signal, CLK, opens the register so data from the previous stage can be clocked into the register.
In the compare/shift register of the present invention, an input register is clocked which connects a bit from a serial bit stream to the first stage of the comparator/shift register. In the first stage a bit in a serial bit stream is connected to a first input of a MUX and to a first input to an XNOR circuit. The bit from the serial bit stream is also connected to the first input of XNOR circuits in all subsequent stages of the comparator/shift register. The second input of the XNOR circuit in the first stage is connected to a first reference bit. The second input of an XNOR circuit in the second stage is connected to a second reference bit. In the third stage the second input to an XNOR circuit is connected to a third reference bit, and continuing in like manner until the last stage where the last reference bit is connected to the second input of an XNOR circuit in the last stage. The output of the XNOR circuit in the first stage is connected to the second input of the MUX. The MUX is controlled with a select signal that chooses the output of the XNOR for use in a compare configuration, or the serial hit stream for use as a shift register. The output of the MUX is connected to the input of the first stage output register. When a clock signal is applied to the register, the signal from the MUX is captured by the register and passed on to the second state.
In the second stage the output of the first stage register connects bits from the serial bit stream to a first input of an AND circuit and to a first input of a MUX. The output of the second stage XNOR circuit is connected to the second input of the AND circuit. The output of the AND circuit is connected to the second input of the MUX. A select signal selects either the serial bit stream to connect to the input of the second stage output register or the output of the AND circuit. When the circuitry is being used as a shift register the MUX select signal selects the serial bit stream, and when the circuitry is being used as a compare circuit the output of the AND circuit is connected to the second stage output register.
When being used as a compare circuit, the compare signal from the first stage is connected to the first input of the second stage AND circuit. The second stage compare signal is connected front the Output of the second stage XNOR circuit to the second input of the AND circuit. When a bit comparison is made in the first stage and in the second stage, the AND circuit produces a signal signifying that there was a comparison in both stages to the respective reference bits. If either the first stage or the second stage does not produce a comparison between bits in the serial bit stream, the AND circuit output produces a no compare signal which is connected to the second stage MUX. The output of the second stage MUX is connected to output register of the second stage. When a clock signal is applied to the second stage register the results of the AND of the first stage results and the second stage results are connected to the third stage. The ANDing of the first stage compare results with the second stage compare results are an accumulation of the compare results from the first stage and the second stage.
The accumulation of the compare results from the first two stages is connected to the third stage through the clocking of the second stage output register. In like manner to the second stage, the third stage compare results is accumulated in the third stage AND circuit with the accumulated results of the previous two stages. The output of the third stage becomes the accumulation of the compare of the first, second and third stages. The accumulation of compare results continues in like manner in subsequent stages until the nth and last stage produces a total compare results for n contiguous bits in the serial bit stream.
The first bit in a serial bit stream is connected to the XNOR compare circuit in the first stage and all the subsequent stages of the comparator from the second stage through the nth and last stage. If the first bit compares to a first predetermined value in the first stage, the same first bit may or may not indicate a comparison in the next nxe2x88x921 bits. When there is not a comparison in the n stages of the compare circuitry, the non-comparison will accumulate in subsequent stages with subsequent bits to produce a no comparison at the output of the last stage for the last n bit in the serial bit stream.
The second bit in the serial bit stream is connected to all the compare circuit in all stages of the comparator from the first stage to the nth and last stage. When the second hit produces a comparison to the second predetermined reference value in the second stage compare circuit, the compare results is accumulated by ANDing the second stage compare results from the first stage results for the first bit. If the first bit compares with the first predetermined value and the second bit compares with the second predetermined value, the accumulated results through two stages is a compare. While this is going on, the first stage is comparing the second bit in the serial bit stream with the first predetermined reference value, and all subsequent stages to the second stage are comparing the second bit to the predetermined reference values connected to each of the subsequent stages The compare results in the first stage to the second bit in the serial hit stream will be clocked into the second stage as the compare accumulation results of the second stage are clocked into the third stage.
The second bit in the serial bit stream is connected to all of the compare XNOR circuits in the n stages of the compare circuitry. If the third bit does not compare to the third predetermined reference value in the XNOR compare circuit in the third stage then the ANDing of the third compare results with the accumulation of the comparison of first two bits will indicate a no comparison for the first three bit is the serial bit stream. If the third bit compares to the third predetermined value, then the accumulated compare results of the third stage will indicate a comparison for the first three bits in the serial bit stream. This comparison of the input data stream continues by exclusive NORing the input data stream with the predetermined reference values in each of the compare stages. When the last stage outputs an accumulated compare signal from its AND circuit, then all compare stages found a comparison between their predetermined reference value and a bit in the serial bit stream, and the last n bits of the serial bit stream is a match to the n predetermined values.